#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define N 7


// FUNCTION: 定义动态数组
typedef int ElemType;

typedef struct {
	ElemType *elem;//存储元素的起始地址
	int TableLen;//元素个数
} SSTable;


// FUNCTION: 随机数生成
void ST_Init(SSTable &ST, int len) {
	// NOTE: 变量初始化
	// STEP: 为动态数组设置界限
	ST.TableLen = len;

	// STEP: 申请动态数组实际空间
	ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);

	// STEP: 存放赋值变量是的索引
	int i;


	// NOTE: 生成随机数
	srand(time(NULL));


	// NOTE: 将数据存储到数组中
	// HINT: 为啥这里零号位置也存放了随机了数据？是为折半查找服务的。
	for (i = 0; i < ST.TableLen; i++) {
		ST.elem[i] = rand() % 100;
	}
}


// FUNCTION: 输出数组中全部元素
void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}

	printf("\n");
}


// FUNCTION: 局部二路归并
// @param: low表示前一段序列的起始索引；mid表示前一段序列的结束索引；high表示后一段序列的结束索引
// 原始数据：49,38,65,97,76,13,27
void Merge(ElemType A[], int low, int mid, int high) {
	// NOTE: 变量声明
	// STEP: 定义辅助数组B，其大小与A数组等大
	// HINT: 为了降低操作次数
	ElemType B[N];

	// STEP: 申请其他的临时变量。用于作为索引
	int i, j, k;


	// NOTE: 数据预处理
	// HINT: 将A数组low到high之间的所有元素，复制到辅助数组B中。（用索引k进行一一对应）
	for (k = low; k <= high; k++) {
		B[k] = A[k];
	}


	// NOTE: 实现归并两个有序数组
	// HINT: 索引i指向的是：辅助数组中，前一段有序数组的起始；索引j指向的是：辅助数组中，后一段有序数组的起始；索引k指向的是：原数组中，前一段有序数组的起始；
	// REVIEW: 每一轮循环，比较两段数组中索引i、j所指元素谁更小？将较小者放回原数组索引k所指的位置。然后，索引k后移一位。较小者出自的数组索引，也后移一位。
	// STEP: 当两段数组都有未比较元素的情况
	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
		if (B[i] <= B[j]) {
			A[k] = B[i++];
		} else {
			A[k] = B[j++];
		}
	}


	// STEP: 没有归并完的部分，直接复制到原数组尾部
	while (i <= mid) {
		A[k++] = B[i++];
	}
	while (j <= high) {
		A[k++] = B[j++];
	}
}


// FUNCTION: 二路归并排序的主实现逻辑
// REVIEW: 我们可以认为单个元素是自然有序的。所以，我
void Merge_Sort(ElemType A[], int low, int high) {
	// 递归允许条件
	if (low < high) {
		// 确定拆分中点
		int mid = (low + high) / 2;

		// 对左侧的序列进一步二分
		Merge_Sort(A, low, mid);

		// 对右侧的序列进一步二分
		Merge_Sort(A, mid + 1, high);

		// 实现归并
		Merge(A, low, mid, high);
	}
}



/*

int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	// STEP: 声明动态数组
	SSTable ST;

	// STEP: 声明一组数
	ElemType A[N] = {49, 38, 65, 97, 76, 13, 27};


	// NOTE: 数组元素赋值
	// HINT: 实际申请了N个元素空间
	ST_Init(ST, N);
	memcpy(ST.elem, A, sizeof(A));

	printf("Original sequence is: ");
	ST_print(ST);


	// NOTE: 堆排序
	// HINT: 王道书零号元素不参与排序
	Merge_Sort(A, 0, N);


	return 0;
}

*/







